1. Field of the Invention
This invention relates to a block encryption system and more particularly to a method and apparatus for encrypting a long plaintext block using an encryption procedure intended for relatively short blocks.
2. Description of the Related Art
Encryption schemes fall into two general categories: symmetric encryption systems and asymmetric encryption systems. In symmetric encryption systems, such as those conforming to the Data Encryption Standard (DES), the same key is used by the originator to encrypt data (i.e., convert plaintext to ciphertext) and by the recipient to decrypt the same data (i.e., convert ciphertext back to ciphertext). Symmetric encryption schemes can often be implemented very efficiently, but suffer the disadvantage of requiring the prior exchange of encryption keys over a secure communications channel.
Asymmetric encryption systems, or public key encryption systems as they are usually called, use one key to encrypt data while using another key to decrypt the same data. In a public key encryption system, an intended recipient of data generates a key pair consisting of an encryption key, which is made public, and a corresponding decryption key, which is kept private and not shared with others. The keys are generated in such a manner that the private key cannot be derived from knowledge of the corresponding public key; hence, only the intended recipient having the private key can decrypt a ciphertext message generated using the public key. An important advantage public key encryption systems have over symmetric systems is that they do not require the exchange of secret key information; two parties can establish a secure two-way communication by exchanging public keys that they have generated. For this reason, asymmetric encryption systems are often used for the secret key exchange required in symmetric encryption systems.
Perhaps the most well-known public key encryption system is the RSA encryption system, named after its originators and described in R. L. Rivest et al., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, vol. 21, no. 2, pp. 120-126 (1978). RSA encryption systems typically have encryption blocks on the order of 512 bits and can be computationally quite intensive. Recently, however, so-called elliptic curve systems have been described in such references as N. Koblitz, "Elliptic Curve Cryptosystems", Mathematics of Computation, vol. 48, no. 177, pp. 203-209 (January 1987), and A. Menezes, Elliptic Curve Public Key Cryptosystems (1993). Like the RSA encryption system, elliptic curve systems are public key systems with public encryption keys and private decryption keys. Elliptic curve systems typically have relatively short key and encryption block sizes, on the order of 160 bits for each, but have a cryptographic strength that is comparable to that of longer-block RSA encryption systems. Elliptic curve systems thus represent an attractive combination of cryptographic strength and computational efficiency.
Since elliptic curve encryption systems are public key systems, one use of such systems might be to distribute keys. Thus, user A might use a public elliptic curve key to encrypt a symmetric key (e.g., a DES key) for distribution to user B. But a problem arises, since the symmetric key is normally contained in a key block (e.g., a 512-bit block) which is much longer than the elliptic curve encryption block, which, as noted above, may be on the order of only 160 bits. Although the key block can be divided into multiple encryption blocks of sufficiently small size, the additional encryption operations required for the individual encryption blocks vitiate to some extent the natural advantages of elliptic curve systems in terms of their computational efficiency. What is needed is a method of key encryption that can be used with an elliptic curve algorithm which will permit a large key block to be encrypted with a secret elliptic curve key of much shorter length.
The above-identified copending application Ser. No. 08/603,771 discloses a system for encrypting a plaintext block (such as a key block) using a block encryption algorithm (such as an elliptic curve algorithm) having a block size smaller than that of the plaintext block. As disclosed in that application, the plaintext block is transformed into a masked plaintext block using an invertible transformation optionally dependent on additional data outside the plaintext block. The additional data may comprise control information, a control vector or other information available to the recipient and not requiring encryption. The transformation is defined such that (1) the original plaintext block is recoverable from the masked key block and optional additional information and (2) each bit of the masked plaintext block depends on every bit of the original plaintext block. A subportion of the masked plaintext block is encrypted using the encryption algorithm to generate an encrypted portion of the masked plaintext block. A ciphertext block is generated from the thus encrypted portion of the masked plaintext block and the remaining portion of the masked plaintext block. The ciphertext block is transmitted to a recipient, who reverses the procedure to recover the original plaintext block.
Either the plaintext block or the additional data on which the transformation is optionally dependent is uniquely modified for each encryption of a plaintext block, using an incrementing counter, time stamp, random number or other mechanism to thwart certain cryptanalytic attacks.
Since the entire masked plaintext block is necessary to reconstruct the original plaintext block and since the encrypted portion cannot be derived from the remaining portion, the remaining portion of the masked plaintext block may be transmitted to the recipient in unencrypted form. The discloses system thus permits a long key block to be encrypted with a short encryption key. In an exemplary embodiment, an elliptic curve algorithm having a block size on the order of 160 bits is used to encrypt a 512-bit block containing a symmetric encryption key.
The copending application teaches the use of three or more rounds in a masking process prior to asymmetric encryption. However, the copending application provides no explicit guidance on determining how to achieve security with a minimum number of rounds in various scenarios. Thus, it has been suggested that the system described in the copending application that the system may expose secret information, depending on the location of that information in the input block.
It has been suggested that this exposure may be avoided by adding a masking round, for a total of four masking rounds, or by locating the secret information in the part of the input block that is first used to mask the other part. However, both of these alternatives have disadvantages. Adding another masking round increases the computational expense, while locating the secret information in a particular part of the input block may not always be possible in a particular situation.
Thus, identification of the exact number of rounds needed to achieve security in varying scenarios is important. If fewer masking rounds are performed than are required, then the system may be insecure. On the other hand, if more masking rounds are performed than are required, then the performance of the system may be unnecessarily degraded.